#ifndef COMPILE_PRINCIPLE_TOOL
#define COMPILE_PRINCIPLE_TOOL

#include <vector>
#include <map>
#include <set>
#include <functional>
#include <cstring>
#include <ostream>


namespace tool{
class UnionFindSet{
	int n;
	int *root;
public:
	UnionFindSet(int _n):n(_n){
		root = new int[n];
		for (int i = 0; i < n; ++i)
			root[i] = i;
	}
	~UnionFindSet(){if (root) delete root; root = 0;}
	int find(int t)const{return root[t] == t ? t : root[t] = find(root[t]);}
	void merge(int u, int v){root[find(u)] = find(v);}
	friend std::ostream& operator << (std::ostream& os, const UnionFindSet& ufs){
		for (int i = 0; i < ufs.n; ++i)
			os << i << " -> " << ufs.find(i) << std::endl;
		return os;
	}
};

class Graph{
public:
typedef std::vector<std::set<int> > Map;
private:
	int n;			// 点数
	bool *visit;	// 是否访问过
	int *edges;		// 边图
	bool isRev;		// 是否为反向图
	int &edge(int b, int e) const{
		return isRev ? edges[b+e*n] : edges[e+b*n];
	}
	void dfs(int cur, std::function<void(int)> func){
		visit[cur] = true;
		for (int i = 0; i < n; ++i){
			if (!edge(cur,i) || visit[i]) continue;
			visit[i] = true;
			dfs(i, func);
		}
		func(cur);
	}
public:
	Graph(int _n):n(_n),isRev(false){
		edges = new int[n*n];
		visit = new bool[n];
		resetGraph();
	}
	~Graph(){
		if(edges) delete []edges;
		if(visit) delete []visit;
		visit = 0;
		edges = 0;
	}

	/**
	 * 加一条从b到e的边
	 */
	void setEdge(int b, int e){
		edge(b,e) = 1;
	}

	/**
	 * 设置从b到e这条边的权值
	 */
	void setEdge(int b, int e, int weight){
		edge(b,e) = weight;
	}

	/**
	 * 删一条b到e的边
	 */
	void delEdge(int b, int e){
		edge(b,e) = 0;
	}
	/** b与e是否连通 */
	int connect(int b, int e) const{return edge(b, e);}
	/** 将所有边逆向 */
	void reverse(){isRev = !isRev;}

	static void display(const Map &map);

	/**
	 * 砍掉所有的环，求强连通分量
	 * @param ufs 并查集，返回结果的引用参数，ufs.find(i)==j表示原来i节点在现在的j节点内
	 * @return 这是分配在堆上、用new申请的
	 */
	Graph* killRing(Map &map);

	friend std::ostream& operator << (std::ostream& os, const Graph& graph){
		for (int i = 0; i < graph.n; ++i)
			for (int j = 0; j < graph.n; ++j)
				if (graph.connect(i,j))
					os << i << " -> " << j << std::endl;
		return os;
	}

	/**
	 * 重置图，清零所有的边，并且设定为非反向图，所有皆未访问
	 */
	void resetGraph(){
		memset(edges, 0, sizeof(int)*n*n);
		isRev = false;
		resetVisit();
	}
	void resetVisit(){memset(visit, 0, sizeof(bool)*n);}

	/**
	 * 求解传递闭包
	 */
	void closure();

	int dim() const{return n;}

	void foreach(std::function<void(int,int)> func);
};
}

#endif



























